#include "seq-list.cpp"

/***
 * 插入排序
 * 基本思路: 将一个记录插入到已经排好序的有序表中
 * 实现过程: 双层循环
 * 时间复杂度: 平均 O(n^2) 最优O(n) 最坏O(n^2)
 * 空间复杂度: O(1)
 * 稳定性: 稳定
 * */

void sort(SqList &L)
{
    for (int i = 1; i < L.length; i++)
    {
        for (int j = 0; j < i && L.data[i] < L.data[j]; j++)
            swap(L, i, j);
        // 输出过程
        printf("第 %d 趟:", i);
        printList(L);
    }
}

int main()
{
    SqList L;
    int data[6] = {6, 5, 3, 2, 7, 1};
    L.data = data;
    L.length = 6;
    printList(L);
    sort(L);
    printList(L);
    return 0;
}




